import java.util.Arrays;
//NOTES FOR FINAL: Learn how to implement a disjoint set to make a maze.
/**
 * Done in O(nlog(n)) time and (n) space in the sequence finder. Worked with coauthors to debug.
 * @author Timothy Ginder
 * @coauthor Chris 
 * @coauthor Bob
 * @version
 */
public class HW_5_1_ver3 {
	
	/**
	 * The test for this problem, should provide a longest increasing subsequence of 6.
	 * Note: This does not find the contiguous version!
	 * @param arg the console input.
	 */
	public static void main(String[] arg) {
		String[] hello = new String[10];
		hello[0] = "10";
		hello[1] = "99";
		hello[2] = "20";
		hello[3] = "44";
		hello[4] = "55";
		hello[5] = "67";
		hello[6] = "20";
		hello[7] = "44";
		hello[8] = "55";
		hello[9] = "66";
		
		int longestSequence = LongestCommonSubsequence(hello, sorting(hello));
		System.out.println("The longest ascending sequnce in the string is: " + longestSequence);
		
	}
	
	/**
	 * Used to sort the string for input into the subsequence finder.
	 * @param unorderedInput unsorted string array.
	 * @return a sorted string array.
	 */
	public static String[] sorting(String[] unorderedInput) {
		String[] sorted = new String[unorderedInput.length];
		for (int i = 0; i < unorderedInput.length; i++) {
			sorted[i] = unorderedInput[i];
		}
		Arrays.sort(sorted); //Used because it runs faster than a simple merge sort.
		return sorted;
	}
	

	/**
	 * Finds the longest non contiguous subsequence via 2*n space, 
	 * in a similar fashion to the robot coin problem.
	 * @param A unsorted string array. 
	 * @param B sorted string array.
	 * @return the integer of the longest common subsequence.
	 */
	public static int LongestCommonSubsequence(String A[], String B[]) {
		int m[][] = new int[2][B.length + 1];
		for(int i = A.length; i >= 0; i--) {
			int ii = i&1;
			for(int j = B.length; j >= 0; j--) {
				if(i == A.length || j == B.length) {m[ii][j] = 0; continue;}
				if(convertString(B[j]) == convertString(A[i])) {
					m[ii][j] = 1 + m[1-ii][j+1];
				}
				else {
					m[ii][j] = Math.max(m[ii][j+1], m[1-ii][j]);
				}
			}
		}	
		return m[0][0];
	}
	
	public static String[] trackList(String A[], String B[]) {
		boolean endOfSubList = false;
		for (int i  = 0; i < A.length; i++) {
			for (int j = 0; j < B.length; j++) {
				if (endOfSubList) {
					
				}
			}
			
		}
		
		return null;
	}
	
	/**
	 * This method finds the integer value of a two digit string.
	 * Used to ensure the numbers behave correctly.
	 * @param str the string of numbers to convert to an integer.
	 * @return the integer value of the string.
	 */
	public static int convertString(String str) {
			int first = 10*(str.charAt(0) - 48);
			int second = str.charAt(1) - 48;
			return (first + second);
	}
}
